package main.adt.queue;

/**
 * Created by july on 2015/12/23.
 *
 * 队列的链式存储---链队列
 *
 * 常用操作：
 * 1、初始化建立一个空队列
 * 2、返回队列的长度，返回队列中数据元素个数。
 * 3、加入元素(入队):向队列的rear端插入一个数据元素，队列长度+1
 * 4、删除元素(出队)：从队列的front端删除一个数据元素，队列长度-1，该方法通常返回被删除的数据元素
 * 5、访问队列的前端元素：返回队列的front端的数据元素，但不删除。
 * 6、判断是否为空队列，若为空返回true，不为空返回false。
 * 7、清空队列
 */
public class LinkedQueue<E> {

    private int size;       //元素个数
    private Node front;     //队头指针
    private Node rear;      //队尾指针

    public LinkedQueue(){
        front = rear = null;
    }

    public LinkedQueue(E element){
        front = rear = new Node(element,null);
        size++;
    }

    /**
     * 入队
     * 只要内存空间允许，可以不断进行入队操作而不用担心队满问题
     * @param element
     */
    public void add(E element){
        if(size == 0){
            front = rear = new Node(element,null);
        }else{
            Node newNode = new Node(element,null);
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    /**
     * 出队
     * 只要队列中有元素就可以一直执行出队操作，该操作不会出现假满问题
     * @return
     */
    public E remove(){
        if(size == 0){
            throw new NullPointerException("队列为空，无法删除队头元素");
        }
        Node oldNode = front;
        front = front.next;
        oldNode.next = null;
        size--;
        return oldNode.data;
    }

    /**
     * 访问队头元素
     * @return
     */
    public E get(){
        if(size == 0){
            throw new NullPointerException("队列为空，无法访问队头元素");
        }
        return front.data;
    }

    /**
     * 判断是否为空队列
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 返回队列的长度
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 清空队列
     */
    public void clear(){
        front = rear = null;
        size = 0;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     */
    @Override
    public String toString(){
        if(size == 0){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        for(Node current = front;current != null;current = current.next){
            if(current.data != null){
                sb.append(current.data.toString()).append(",");
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

    private class Node{
        private E data;      //数据域
        private Node next;   //指针域,指向它的直接后继

        protected Node(E element, Node next) {
            this.data = element;
            this.next = next;
        }
    }
}
